package simple;

/**
 * 给定一个数组 prices ，它的第i 个元素prices[i] 表示一支给定股票第 i 天的价格。
 * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
 * 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
 * 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class BestTimeToBuyAndSellStock {
    /**
     * 这个乍一看还感觉挺难的。如果非要用dp的思路去想这道题，确实有点绕。
     * 有一个十分简单的方法，就是低买高卖。用一个变量来记录目前出现过最低的股价。然后之后的每一天跟这个最低股价最相减。
     * 然后得到的利润最大值记录下来。
     * */
    class Solution {
        public int maxProfit(int[] prices) {
            if(prices.length < 2){
                return 0;
            }
            int min = prices[0];
            int profit = 0;
            for (int i=1; i < prices.length; i++){
                profit = Math.max(profit,prices[i] - min);
                min = Math.min(min,prices[i]);
            }
            return profit;
        }
    }
}
